package com.wtgroup.demo.mianshi.算法.二分法;

import cn.hutool.core.util.ArrayUtil;
import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Sout;

/**
 * 二分查找
 *
 * @author dafei
 * @version 0.1
 * @date 2021/4/11 14:13
 */
public class BinarySearch {

    
    public static void main(String[] args) {
        
        Judger.of(() -> {
            int[] arr = RandomUtil.range(RandomUtil.randomInt(0, 50), RandomUtil.randomInt(0, 100));
            // int[] arr = {1,2,3,4};
            int target = 18;
            int res = new BinarySearch().biSearch_recursion(arr, target);
            int refer = ArrayUtil.indexOf(arr, target);
            if (res != refer) {
                Sout.println("res:", res, "refer:", refer);
                Sout.println(arr);
            }

            return res == refer;
        })
        .start().print();

    }



    public int biSearch_recursion(int[] arr, int target) {
        return biSearch_recursion0(arr, target, 0, arr.length - 1);
    }

    private int biSearch_recursion0(int[] arr, int target, int lo, int hi) {
        if (lo > hi) {
            return -1;
        }

        // int mid = lo + (hi - lo) / 2;
        int mid = (lo + hi) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return biSearch_recursion0(arr, target, mid + 1, hi);
        } else {
            return biSearch_recursion0(arr, target, lo, mid - 1);
        }
    }

    public int search(int[] arr, int key, int left, int right) {
        while (left <= right) {
            int mid = left + ((right-left)>>1);
            if (key == arr[mid]) {
                return mid;
            } else if(key < arr[mid]){
                right = mid-1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }

}
